package org.example.day01;

import java.util.*;

/**
 * @author zlxad
 * @version 1.0
 * @description: TODO+
 * 有一个总空间为100字节的堆，现要从中新申请一块内存，内存分配原则为优先紧接着前一块已使用内存分配空间足够且最接近申请大小的空闲内存。
 * @date 2024/3/11 15:22
 */
public class test019 {

    // 堆的总大小
    private static final int HEAP_SIZE = 100;
    // 已分配的内存块列表
    private List<int[]> allocatedBlocks = new ArrayList<>();

    /**
     * 分配内存
     * @param requestedSize 期望申请的内存字节数
     * @return 成功分配的内存起始地址，若申请失败则返回-1
     */
    public int allocateMemory(int requestedSize) {
        // 非法申请，直接返回-1
        if (requestedSize <= 0 || requestedSize > HEAP_SIZE) {
            return -1;
        }

        // 空闲内存块列表
        List<int[]> freeBlocks = new ArrayList<>();
        int start = 0;

        // 根据偏移地址排序已分配的内存块
        allocatedBlocks.sort(Comparator.comparingInt(a -> a[0]));

        // 遍历已分配的内存块
        for (int[] block : allocatedBlocks) {
            int offset = block[0];
            int size = block[1];
            // 判断已分配的内存块是否合法
            if (offset < start || offset + size > HEAP_SIZE) {
                return -1;
            }
            // 如果两个内存块之间有足够的空闲空间，将其添加到空闲内存块列表中
            if (offset - start >= requestedSize) {
                freeBlocks.add(new int[]{start, offset - start});
            }
            start = offset + size;
        }

        // 判断最后一个内存块之后是否有足够的空闲空间
        if (HEAP_SIZE - start >= requestedSize) {
            freeBlocks.add(new int[]{start, HEAP_SIZE - start});
        }

        // 如果没有足够的空闲空间供分配，返回-1
        if (freeBlocks.isEmpty()) {
            return -1;
        }

        // 根据空闲内存块大小从小到大排序
        Collections.sort(freeBlocks, Comparator.comparingInt(a -> a[1]));

        // 遍历空闲内存块，找到大小足够的内存块，返回其起始地址
        for (int[] block : freeBlocks) {
            if (block[1] >= requestedSize) {
                return block[0];
            }
        }

        // 没有找到足够大小的空闲内存块，返回-1
        return -1;
    }

    public static void main(String[] args) {
        test019 allocator = new test019();
        Scanner scanner = new Scanner(System.in);

        System.out.print("请输入期望申请的内存字节数: ");
        int requestedSize = scanner.nextInt();
        scanner.nextLine();

        System.out.println("请输入已分配的内存块，格式为<起始地址> <大小>，输入'end'结束：");
        while (true) {
            String line = scanner.nextLine().trim();
            if (line.equalsIgnoreCase("end")) {
                break;
            } else if (!line.isEmpty()) {
                try {
                    String[] parts = line.split("\\s+");
                    if (parts.length == 2) {
                        int offset = Integer.parseInt(parts[0]);
                        int size = Integer.parseInt(parts[1]);
                        allocator.allocatedBlocks.add(new int[]{offset, size});
                    } else {
                        System.out.println("输入格式错误，请重新输入");
                    }
                } catch (NumberFormatException e) {
                    System.out.println("输入包含非数字字符，请重新输入");
                }
            }
        }

        int offset = allocator.allocateMemory(requestedSize);
        System.out.println("分配的内存起始地址: " + offset);

        scanner.close();
    }

}
